// 给定一个二叉树，我们在树的节点上安装摄像头。

// 节点上的每个摄影头都可以监视其父对象、自身及其直接子对象。

// 计算监控树的所有节点所需的最小摄像头数量。

// 暴露接口
function minCameraCover(root: TreeNode | null): number {
    const { setCam, noCamWatchBySon } = minCameraCover_DpTree(root);
    return Math.min(setCam, noCamWatchBySon);
};

// 树形DP辅助方法
function minCameraCover_DpTree(root: TreeNode | null) {
    // 递归出口
    if (root === null) {
        return {
            setCam: Infinity,
            noCamWatchByDad: 0,
            noCamWatchBySon: 0
        };
    }
    // 拿到左右子树递归的计算结果
    const leftRes = minCameraCover_DpTree(root.left);
    const rightRes = minCameraCover_DpTree(root.right);
    // 如果在当前节点有设置监控
    const setCam: number = 1 + Math.min(
        leftRes.noCamWatchByDad + rightRes.noCamWatchByDad,
        leftRes.setCam + rightRes.noCamWatchByDad,
        leftRes.noCamWatchByDad + rightRes.setCam
    );
    // 如果当前节点未设置监控但其被父节点监控
    const noCamWatchByDad: number = Math.min(
        leftRes.setCam + rightRes.noCamWatchBySon,
        leftRes.noCamWatchBySon + rightRes.setCam,
        leftRes.noCamWatchBySon + rightRes.noCamWatchBySon,
        leftRes.setCam + rightRes.setCam
    );
    // 如果当前节点未设置监控但其被子节点监控
    const noCamWatchBySon: number = Math.min(
        leftRes.setCam + rightRes.setCam,
        leftRes.setCam + rightRes.noCamWatchBySon,
        leftRes.noCamWatchBySon + rightRes.setCam
    );
    // 返回结果对象
    return {
        setCam,
        noCamWatchByDad,
        noCamWatchBySon
    };
}



// 这道题目是一道难度较大的树形动态规划的算法题，主要的难点在于持有状态计算的思考
// 对于一个节点，它有什么状态，仅仅是放与不放相机吗？还有：是否被监控到。
// 节点本身的状态可能是：
// 1.自己放置了相机，
// 2.自己没相机但是被父节点监控
// 3.自己没相机但是被子节点监控
// 我们定义动态规划函数用来计算每一层递归的最小相机放置个数
// 根据上述的状态，得到三个变量：
// 1.setCam ：当前子树 root 有相机情况下的最小相机个数
// 2.noCamWatchByDad：当前子树 root 没有相机，被父亲监控情况下的最小相机个数
// 3.noCamWatchBySon ：当前子树 root 没有相机，被儿子监控情况下的最小相机个数
// 然后思考递归的终点，或者说是动态规划计算的起点
// setCam = Infinity，
// 如果当前节点为空，我们肯定不希望这个在这个空节点上放置相机，所以返回Infinity
// noCamWatchByDad = 0，noCamWatchBySon = 0
// 如果当前节点为空，它被父子节点观察情况的个数肯定为0（没有必要观察一个空节点）
// 接下来我们思考枚举的情况
// （1）如果当前节点存在相机，那么目前状态所存在的最小相机数为
// 1（当前节点的相机要算） + min(
//     左子树的setCam + 右子树noCamWatchByDad，
//     左子树的noCamWatchByDad + 右子树的setCam，
//     左子树的noCamWatchByDad + 右子树noCamWatchByDad
// )
// 注意：不存在左右子树同时都有相机的原因是因为局部最优解中不可能存在根、左、右同时出现相机的情况

// （2）如果当前节点不存在相机，且它是被父节点监控到的，那么目前状态所存在的最小相机数为
// min(
//     左子树的setCam + 右子树的noCamWatchBySon,
//     左子树的noCamWatchBySon + 右子树的setCam,
//     左子树的noCamWatchBySon + 右子树的noCamWatchBySon,
//     左子树的setCam + 右子树的setCam
// )

// （3）如果当前节点不存在相机，且它是被子节点监控到的，那么目前状态所存在的最小相机数为
// min(
//     左子树的setCam + 右子树的setCam,
//     左子树的setCam + 右子树的noCamWatchBySon,
//     左子树的noCamWatchBySon + 右子树的setCam
// )

// 根据以上的枚举情况即可求解。